//
// Created by buyongjiu on 2024/4/22.
//

#include <iostream>
#include <algorithm>
#include "../include/Grammar.h"

int Grammar::Scan_CFG_Grammer(std::vector<std::string> corresponding_input) {
    for (auto &st: corresponding_input) {
        if (st.find(" -> ") == std::string::npos) {
            this->start = st.substr(0, st.size() - 1);
            continue;
        }
        std::string left = st.substr(1, st.find(" -> ") - 1);
        if (this->V_map.find(left) == this->V_map.end()) {
            V *left_production = new V(VN, left);
            this->V_map[left] = left_production;
            this->V_set.insert(left_production);
        }
        std::vector<V *> right_production;
        std::string temp = "";
        for (auto &c: st.substr(st.find(" -> ") + 4)) {
            if (c == ' ') {
                if (temp[0] == '@') {
                    if (this->V_map.find(temp.substr(1)) == this->V_map.end()) {
                        V *v = new V(VN, temp.substr(1));
                        this->V_map[temp.substr(1)] = v;
                        this->V_set.insert(v);
                    }
                    right_production.push_back(V_map[temp.substr(1)]);
                } else {
                    if (this->V_map.find(temp) == this->V_map.end()) {
                        V *v = new V(VT, temp);
                        this->V_map[temp] = v;
                        this->V_set.insert(v);
                    }
                    right_production.push_back(V_map[temp]);
                }
                temp = "";
            } else {
                temp += c;
            }
        }
        this->productions[this->V_map[left]].push_back(right_production);

    }

    return 0;
}

void Grammar::EliminateLeftRecursion() {
    this->EliminateindirectLeftRecursion();
    this->EliminatedirectLeftRecursion();
}

void Grammar::EliminateindirectLeftRecursion() {
    // A -> aB (1)
    // A -> Bb (2)
    // B -> Ac (3)
    // B -> d  (4)
    // 用12替换3中A
    // 需要找到当前产生式右部的第一个符号，判断是否为非终结符
    // 如果是继续找这个非终结符的右部，看这个右部的开头是否为最开始产生式的左部，如果有则代表存在间接左递归
    // 需要将这个后者式子中的A全部替换成A的式子，同时删除后者式子


    std::string left = "";
    std::string rightfirst = "";

    for (auto &pro: this->productions) {
        left = pro.first->name;
        for (auto &right_pro: pro.second) {
            if (right_pro[0]->type == VN && right_pro[0]->name != left) {
                rightfirst = right_pro[0]->name;
                for (auto &B_pro: this->productions[V_map[rightfirst]]) {
                    if (B_pro[0]->name == left) {
                        std::cout << "CFG have the indirect left recursion" << std::endl;
                    }
                }
            }
        }
    }


}

void Grammar::EliminatedirectLeftRecursion() {
    for (auto &pro: this->productions) {
        std::string left = pro.first->name;
        std::string rightfirst;
        for (auto &right_pro: pro.second) {
            rightfirst = right_pro[0]->name;
            if (left == rightfirst) {
                // 创建新状态
                if (V_map.find(left + "'") == V_map.end()) {
                    V *v = new V(VN, left + "'");
                    this->V_map[left + "'"] = v;
                    this->V_set.insert(v);
                }
                for (auto &A: this->productions[V_map[left]]) {
                    if (A[0]->name == left) {
                        std::vector<V *> temp;
                        for (int i = 1; i < A.size(); i++) {
                            temp.push_back(A[i]);
                        }
                        temp.push_back(V_map[left + "'"]);
                        this->productions[V_map[left + "'"]].push_back(temp);
                        A.clear();
                    }
                }
                for (auto &pro1: this->productions[V_map[left]]) {
                    // 向所有其他符号开头的产生式中加入新状态
                    if (pro1[0]->name != left) {
                        pro1.push_back(V_map[left + "'"]);
                    }
                }
                // A -> Aa
                // A -> Ab
                // A -> Ac
                // A -> d
                // 用A'替换A
                // 即A -> dA'
                // A' -> aA'
                // 找到该left的其他产生式
                // 让其他产生式之后加上一个新的状态
                // 这个新的状态可以推出当前产生式去掉最开始的状态

                // 找到之前清空的表达式，将其从map中删除
                for (auto &innerVector: this->productions) { // 遍历 map 中的每个键值对
                    if (innerVector.first->name == left) {
                        auto &vec = innerVector.second; // 获取与键关联的 vector<vector>
                        // 移除 vector 中的所有空 vector
                        vec.erase(std::remove_if(vec.begin(), vec.end(), [](const std::vector<V *> &v) {
                            return v.empty(); // 条件为 true 时，表示 vector 是空的
                        }), vec.end());
                    }
                }
                break;
            }
        }
    }
}

void Grammar::ExtendGrammar() {
    std::string s = this->start + "'";
    this->V_map[s] = new V(VN, s);
    this->V_set.insert(this->V_map[s]);
    this->productions[this->V_map[s]].push_back({this->V_map[start]});

}

void Grammar::get_First_Helper(V* v) {
    if (v->type == VT && v->name != "%") {
        if(std::find(this->First[v->name].begin(), this->First[v->name].end(), v) == this->First[v->name].end()) {
            this->First[v->name].push_back(v);
            return;
        }
    }
    if (v->type == VN) {
        for(auto &pro: this->productions[v]) {
            if (pro[0]->type == VT) {
                if(std::find(this->First[v->name].begin(), this->First[v->name].end(), pro[0]) == this->First[v->name].end()) {
                    this->First[v->name].push_back(pro[0]);
                }
            } else if (pro[0]->type == VN) {
                get_First_Helper(pro[0]);
                for(auto &item: this->First[pro[0]->name]) {
                    if (item->name == "%") {
                        if (pro.size() == 1) {
                            if(std::find(this->First[v->name].begin(), this->First[v->name].end(), item) == this->First[v->name].end()) {
                                this->First[v->name].push_back(item);
                            }
                        } else {
                            get_First_Helper(pro[1]);
                            for(auto &item: this->First[pro[1]->name]) {
                                if(std::find(this->First[v->name].begin(), this->First[v->name].end(), item) == this->First[v->name].end()) {
                                    this->First[v->name].push_back(item);
                                }
                            }
                        }
                    } else {
                        if(std::find(this->First[v->name].begin(), this->First[v->name].end(), item) == this->First[v->name].end()) {
                            this->First[v->name].push_back(item);
                        }
                    }
                }
            }
        }
    }
}

void Grammar::get_First() {
    for(auto &v: this->V_set) {
        get_First_Helper(v);
    }
}